package leetcode;

//假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
//每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
//注意：给定 n 是一个正整数。
//示例 1：
//输入： 2
//输出： 2
//解释： 有两种方法可以爬到楼顶。
//1.  1 阶 + 1 阶
//2.  2 阶
//示例 2：
//输入： 3
//输出： 3
//解释： 有三种方法可以爬到楼顶。
//1.  1 阶 + 1 阶 + 1 阶
//2.  1 阶 + 2 阶
//3.  2 阶 + 1 阶

public class problems_070 {

    public static void main(String[] arge) {
        System.out.println(new Solution().climbStairs(45));
    }

    static class Solution {
        public int climbStairs(int n) {
            if (n == 1) {
                return 1;
            }
            int[] dp = new int[n + 1];
            dp[1] = 1;
            dp[2] = 2;
            for (int i = 3; i <= n; i++) {
                dp[i] = dp[i - 1] + dp[i - 2];
            }
            return dp[n];
        }

        /**
         * 推测处理
         * 比如总台阶为N,一阶为X,二阶为Y，则 X + 2Y = N
         * 从X = N开始，处理
         * Y = 1时，组合方式有(N-1)种
         * Y = 2时，组合方式有(N-3) + 种
         */



        // 分治法处理(性能消耗有点大)
//        private int find(int lastNum){
//            if(lastNum <= 2){
//                return lastNum;
//            }else {
//                return find(lastNum - 1) + find(lastNum - 2);
//            }
//        }
    }
}
